package leetcode.code0689;

import leetcode.helper.MaxDebug;

/**
 * 执行用时：23 ms, 在所有 Java 提交中击败了8.82%的用户
 *
 * 内存消耗：43.1 MB, 在所有 Java 提交中击败了11.76%的用户
 *
 * 通过测试用例：43 / 43
 *
 * @author CaoYu
 * @date 2021年12月8日
 * @description
 */
public class Solution6 extends S689 {

	@Override
	public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
		int Len = nums.length;
		int[] sum = new int[Len + 1];
		for (int i = 1; i <= Len; i++) {
			sum[i] = nums[i - 1] + sum[i - 1];
		}
		int[][] dp = new int[4][Len + 1];
		int[][] ans = new int[4][Len + 1];
		for (int i = 1; i <= 3; i++) {
			for (int j = i * k; j <= Len - (3 - i) * k; j++) {
				if (dp[i][j - 1] >= dp[i - 1][j - k] + sum[j] - sum[j - k]) {
					dp[i][j] = dp[i][j - 1];
					ans[i][j] = ans[i][j - 1];
				} else {
					dp[i][j] = dp[i - 1][j - k] + sum[j] - sum[j - k];
					ans[i][j] = j - k;
				}
			}
		}
		int ans1 = ans[3][Len];
		int ans2 = ans[2][ans1];
		int ans3 = ans[1][ans2];
		return new int[] { ans3, ans2, ans1 };
	}

	public static void main(String[] args) {
		Solution6 so = new Solution6();
		MaxDebug.debug14(so);
	}

}
